Second half of C++17's splicing maps and sets This commit adds a merge member function to all the map and set containers, which splices nodes from the source container. This completes support for P0083r3. Differential revision: https://reviews.llvm.org/D48896 git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@345744 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__hash_table b/include/__hash_table index c77de96..69ed8dd 100644 --- a/include/__hash_table +++ b/include/__hash_table
@@ -1058,8 +1058,26 @@ ); } +private: + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_multi_prepare(size_t __cp_hash, + value_type& __cp_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_multi_perform(__node_pointer __cp, + __next_pointer __pn) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_unique_prepare(size_t __nd_hash, + value_type& __nd_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; + +public: + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1170,6 +1188,9 @@ _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1177,6 +1198,9 @@ template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1849,73 +1873,112 @@ } } + +// Prepare the container for an insertion of the value __value with the hash +// __hash. This does a lookup into the container to see if __value is already +// present, and performs a rehash if necessary. Returns a pointer to the +// existing element if it exists, otherwise nullptr. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( + size_t __hash, value_type& __value) { - __nd->__hash_ = hash_function()(__nd->__value_); size_type __bc = bucket_count(); - bool __inserted = false; - __next_pointer __ndptr; - size_t __chash; + if (__bc != 0) { - __chash = __constrain_hash(__nd->__hash_, __bc); - __ndptr = __bucket_list_[__chash]; + size_t __chash = __constrain_hash(__hash, __bc); + __next_pointer __ndptr = __bucket_list_[__chash]; if (__ndptr != nullptr) { for (__ndptr = __ndptr->__next_; __ndptr != nullptr && __constrain_hash(__ndptr->__hash(), __bc) == __chash; __ndptr = __ndptr->__next_) { - if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_)) - goto __done; + if (key_eq()(__ndptr->__upcast()->__value_, __value)) + return __ndptr; } } } + if (size()+1 > __bc * max_load_factor() || __bc == 0) { - if (size()+1 > __bc * max_load_factor() || __bc == 0) - { - rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), - size_type(ceil(float(size() + 1) / max_load_factor())))); - __bc = bucket_count(); - __chash = __constrain_hash(__nd->__hash_, __bc); - } - // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__nd->__next_ != nullptr) - __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); - } - else - { - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - } - __ndptr = __nd->__ptr(); - // increment size - ++size(); - __inserted = true; + rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), + size_type(ceil(float(size() + 1) / max_load_factor())))); } -__done: -#if _LIBCPP_DEBUG_LEVEL >= 2 - return pair<iterator, bool>(iterator(__ndptr, this), __inserted); -#else - return pair<iterator, bool>(iterator(__ndptr), __inserted); -#endif + return nullptr; +} + +// Insert the node __nd into the container by pushing it into the right bucket, +// and updating size(). Assumes that __nd->__hash is up-to-date, and that +// rehashing has already occurred and that no element with the same key exists +// in the map. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( + __node_pointer __nd) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__nd->__hash(), __bc); + // insert_after __bucket_list_[__chash], or __first_node if bucket is null + __next_pointer __pn = __bucket_list_[__chash]; + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__nd->__next_ != nullptr) + __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); + } + else + { + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + } + ++size(); } template <class _Tp, class _Hash, class _Equal, class _Alloc> -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) { - __cp->__hash_ = hash_function()(__cp->__value_); + __nd->__hash_ = hash_function()(__nd->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); + + // Insert the node, unless it already exists in the container. + bool __inserted = false; + if (__existing_node == nullptr) + { + __node_insert_unique_perform(__nd); + __existing_node = __nd->__ptr(); + __inserted = true; + } +#if _LIBCPP_DEBUG_LEVEL >= 2 + return pair<iterator, bool>(iterator(__existing_node, this), __inserted); +#else + return pair<iterator, bool>(iterator(__existing_node), __inserted); +#endif +} + +// Prepare the container for an insertion of the value __cp_val with the hash +// __cp_hash. This does a lookup into the container to see if __cp_value is +// already present, and performs a rehash if necessary. Returns a pointer to the +// last occurance of __cp_val in the map. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( + size_t __cp_hash, value_type& __cp_val) +{ size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { @@ -1923,8 +1986,44 @@ size_type(ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } - size_t __chash = __constrain_hash(__cp->__hash_, __bc); + size_t __chash = __constrain_hash(__cp_hash, __bc); __next_pointer __pn = __bucket_list_[__chash]; + if (__pn != nullptr) + { + for (bool __found = false; __pn->__next_ != nullptr && + __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; + __pn = __pn->__next_) + { + // __found key_eq() action + // false false loop + // true true loop + // false true set __found to true + // true false break + if (__found != (__pn->__next_->__hash() == __cp_hash && + key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) + { + if (!__found) + __found = true; + else + break; + } + } + } + return __pn; +} + +// Insert the node __cp into the container after __pn (which is the last node in +// the bucket that compares equal to __cp). Rehashing, and checking for +// uniqueness has already been performed (in __node_insert_multi_prepare), so +// all we need to do is update the bucket and size(). Assumes that __cp->__hash +// is up-to-date. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( + __node_pointer __cp, __next_pointer __pn) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__cp->__hash_, __bc); if (__pn == nullptr) { __pn =__p1_.first().__ptr(); @@ -1938,24 +2037,6 @@ } else { - for (bool __found = false; __pn->__next_ != nullptr && - __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; - __pn = __pn->__next_) - { - // __found key_eq() action - // false false loop - // true true loop - // false true set __found to true - // true false break - if (__found != (__pn->__next_->__hash() == __cp->__hash_ && - key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_))) - { - if (!__found) - __found = true; - else - break; - } - } __cp->__next_ = __pn->__next_; __pn->__next_ = __cp->__ptr(); if (__cp->__next_ != nullptr) @@ -1966,6 +2047,17 @@ } } ++size(); +} + + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +{ + __cp->__hash_ = hash_function()(__cp->__value_); + __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); + __node_insert_multi_perform(__cp, __pn); + #if _LIBCPP_DEBUG_LEVEL >= 2 return iterator(__cp->__ptr(), this); #else @@ -2217,6 +2309,32 @@ } template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( + _Table& __source) +{ + static_assert(is_same<__node, typename _Table::__node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __hash = hash_function()(__src_ptr->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__hash, __src_ptr->__value_); + auto __prev_iter = __it++; + if (__existing_node == nullptr) + { + (void)__source.remove(__prev_iter).release(); + __src_ptr->__hash_ = __hash; + __node_insert_unique_perform(__src_ptr); + } + } +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator @@ -2244,6 +2362,27 @@ return __result; } +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same<typename _Table::__node, __node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __src_hash = hash_function()(__src_ptr->__value_); + __next_pointer __pn = + __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); + (void)__source.remove(__it++).release(); + __src_ptr->__hash_ = __src_hash; + __node_insert_multi_perform(__src_ptr, __pn); + } +} #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Hash, class _Equal, class _Alloc> diff --git a/include/__node_handle b/include/__node_handle index 567f8b0..a9cf3b7 100644 --- a/include/__node_handle +++ b/include/__node_handle
@@ -26,9 +26,6 @@ #if _LIBCPP_STD_VER > 14 -// FIXME: Uncomment this when we support the 'merge' functionality. -// #define __cpp_lib_node_extract 201606L - // Specialized in __tree & __hash_table for their _NodeType. template <class _NodeType, class _Alloc> struct __generic_container_node_destructor;
diff --git a/include/__tree b/include/__tree index 3b3586c..aa7370b 100644 --- a/include/__tree +++ b/include/__tree
@@ -1341,15 +1341,20 @@ #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer); + _LIBCPP_INLINE_VISIBILITY iterator + __remove_node_pointer(__node_pointer) _NOEXCEPT; #if _LIBCPP_STD_VER > 14 template <class _NodeHandle, class _InsertReturnType> @@ -1358,6 +1363,9 @@ template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1365,6 +1373,9 @@ template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template <class _NodeHandle> @@ -1384,7 +1395,7 @@ void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, - __node_base_pointer __new_node); + __node_base_pointer __new_node) _NOEXCEPT; template <class _Key> iterator find(const _Key& __v); @@ -2129,10 +2140,9 @@ } template <class _Tp, class _Compare, class _Allocator> -void -__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent, - __node_base_pointer& __child, - __node_base_pointer __new_node) +void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( + __parent_pointer __parent, __node_base_pointer& __child, + __node_base_pointer __new_node) _NOEXCEPT { __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; @@ -2384,7 +2394,7 @@ template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) +__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { iterator __r(__ptr); ++__r; @@ -2472,6 +2482,30 @@ } template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = + __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + if (__child != nullptr) + continue; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + +template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __tree<_Tp, _Compare, _Allocator>::iterator @@ -2507,6 +2541,28 @@ return iterator(__ptr); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf_high( + __parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Compare, class _Allocator> diff --git a/include/map b/include/map index cfd8280..472ac31 100644 --- a/include/map +++ b/include/map
@@ -167,6 +167,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + void swap(map& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -368,6 +377,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + void swap(multimap& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -926,6 +944,11 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1300,6 +1323,38 @@ { return __tree_.template __node_handle_extract<node_type>(__it.__i_); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -1615,6 +1670,11 @@ typedef __map_node_handle<typename __base::__node, allocator_type> node_type; #endif + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1882,6 +1942,38 @@ return __tree_.template __node_handle_extract<node_type>( __it.__i_); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/include/set b/include/set index f2ce6ea..80cc7b0 100644 --- a/include/set +++ b/include/set
@@ -128,6 +128,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + void swap(set& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -316,6 +325,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + void swap(multiset& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -410,6 +428,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Key, class _Compare, class _Allocator> +class multiset; + template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > class _LIBCPP_TEMPLATE_VIS set @@ -449,6 +470,11 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS set; + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multiset; + _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( @@ -681,6 +707,38 @@ { return __tree_.template __node_handle_extract<node_type>(__it); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -891,6 +949,11 @@ typedef __set_node_handle<typename __base::__node, allocator_type> node_type; #endif + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS set; + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multiset; + // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() @@ -1122,6 +1185,38 @@ { return __tree_.template __node_handle_extract<node_type>(__it); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/include/unordered_map b/include/unordered_map index fc3cfb6..6f60749 100644 --- a/include/unordered_map +++ b/include/unordered_map
@@ -153,6 +153,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_map&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -325,6 +334,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multimap&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -808,6 +826,9 @@ template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; }; +template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> +class unordered_multimap; + template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, class _Alloc = allocator<pair<const _Key, _Tp> > > class _LIBCPP_TEMPLATE_VIS unordered_map @@ -865,6 +886,11 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1188,6 +1214,39 @@ return __table_.template __node_handle_extract<node_type>( __it.__i_); } + + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -1646,6 +1705,11 @@ typedef __map_node_handle<__node, allocator_type> node_type; #endif + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1847,6 +1911,39 @@ return __table_.template __node_handle_extract<node_type>( __it.__i_); } + + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/include/unordered_set b/include/unordered_set index a219fa6..de23ca2 100644 --- a/include/unordered_set +++ b/include/unordered_set
@@ -127,6 +127,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_set&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -282,6 +291,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multiset&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -348,6 +366,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Value, class _Hash, class _Pred, class _Alloc> +class unordered_multiset; + template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > class _LIBCPP_TEMPLATE_VIS unordered_set @@ -385,6 +406,11 @@ typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -590,6 +616,39 @@ { return __table_.template __node_handle_extract<node_type>(__it); } + + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -938,6 +997,11 @@ typedef __set_node_handle<typename __table::__node, allocator_type> node_type; #endif + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1102,6 +1166,39 @@ { return __table_.template __node_handle_extract<node_type>(__key); } + + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/include/version b/include/version index 6e61693..aca84f8 100644 --- a/include/version +++ b/include/version
@@ -110,6 +110,7 @@ # define __cpp_lib_filesystem 201703L # define __cpp_lib_invoke 201411L # define __cpp_lib_void_t 201411L +# define __cpp_lib_node_extract 201606L #endif #if _LIBCPP_STD_VER > 17
diff --git a/test/std/containers/associative/map/map.modifiers/merge.pass.cpp b/test/std/containers/associative/map/map.modifiers/merge.pass.cpp new file mode 100644 index 0000000..4fef242 --- /dev/null +++ b/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
@@ -0,0 +1,149 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <map> + +// class map + +// template <class C2> +// void merge(map<key_type, value_type, C2, allocator_type>& source); +// template <class C2> +// void merge(map<key_type, value_type, C2, allocator_type>&& source); +// template <class C2> +// void merge(multimap<key_type, value_type, C2, allocator_type>& source); +// template <class C2> +// void merge(multimap<key_type, value_type, C2, allocator_type>&& source); + +#include <map> +#include "test_macros.h" +#include "Counter.h" + +template <class Map> +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template <class T> + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::map<int, int> src{{1, 0}, {3, 0}, {5, 0}}; + std::map<int, int> dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {{5,0}})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::map<Counter<int>, int, throw_comparator> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::map<Counter<int>, int, std::less<Counter<int>>> first_map_type; + typedef std::map<Counter<int>, int, comparator> second_map_type; + typedef std::multimap<Counter<int>, int, comparator> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + assert(Counter_base::gConstructed == 0); + { + std::map<int, int> first; + { + std::map<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp b/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp new file mode 100644 index 0000000..71f3c0b --- /dev/null +++ b/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,149 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <map> + +// class multimap + +// template <class C2> +// void merge(map<key_type, value_type, C2, allocator_type>& source); +// template <class C2> +// void merge(map<key_type, value_type, C2, allocator_type>&& source); +// template <class C2> +// void merge(multimap<key_type, value_type, C2, allocator_type>& source); +// template <class C2> +// void merge(multimap<key_type, value_type, C2, allocator_type>&& source); + +#include <map> +#include "test_macros.h" +#include "Counter.h" + +template <class Map> +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template <class T> + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}}; + std::multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::multimap<Counter<int>, int, throw_comparator> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multimap<Counter<int>, int, std::less<Counter<int>>> first_map_type; + typedef std::multimap<Counter<int>, int, comparator> second_map_type; + typedef std::map<Counter<int>, int, comparator> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + assert(Counter_base::gConstructed == 0); + { + std::multimap<int, int> first; + { + std::multimap<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/associative/multiset/merge.pass.cpp b/test/std/containers/associative/multiset/merge.pass.cpp new file mode 100644 index 0000000..516e27d --- /dev/null +++ b/test/std/containers/associative/multiset/merge.pass.cpp
@@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <set> + +// class multiset + +// template <class C2> +// void merge(set<Key, C2, Allocator>& source); +// template <class C2> +// void merge(set<Key, C2, Allocator>&& source); +// template <class C2> +// void merge(multiset<Key, C2, Allocator>& source); +// template <class C2> +// void merge(multiset<Key, C2, Allocator>&& source); + +#include <set> +#include "test_macros.h" +#include "Counter.h" + +template <class Set> +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template <class T> + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multiset<int> src{1, 3, 5}; + std::multiset<int> dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {})); + assert(set_equal(dst, {1, 2, 3, 4, 5, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::multiset<Counter<int>, throw_comparator> set_type; + set_type src({1, 3, 5}, throw_comparator(do_throw)); + set_type dst({2, 4, 5}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multiset<Counter<int>, std::less<Counter<int>>> first_set_type; + typedef std::multiset<Counter<int>, comparator> second_set_type; + typedef std::set<Counter<int>, comparator> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::multiset<int> first; + { + std::multiset<int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::set<int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/associative/set/merge.pass.cpp b/test/std/containers/associative/set/merge.pass.cpp new file mode 100644 index 0000000..0896596 --- /dev/null +++ b/test/std/containers/associative/set/merge.pass.cpp
@@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <set> + +// class set + +// template <class C2> +// void merge(set<key_type, C2, allocator_type>& source); +// template <class C2> +// void merge(set<key_type, C2, allocator_type>&& source); +// template <class C2> +// void merge(multiset<key_type, C2, allocator_type>& source); +// template <class C2> +// void merge(multiset<key_type, C2, allocator_type>&& source); + +#include <set> +#include "test_macros.h" +#include "Counter.h" + +template <class Set> +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template <class T> + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::set<int> src{1, 3, 5}; + std::set<int> dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {5})); + assert(set_equal(dst, {1, 2, 3, 4, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::set<Counter<int>, throw_comparator> set_type; + set_type src({1, 3, 5}, throw_comparator(do_throw)); + set_type dst({2, 4, 5}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::set<Counter<int>, std::less<Counter<int>>> first_set_type; + typedef std::set<Counter<int>, comparator> second_set_type; + typedef std::multiset<Counter<int>, comparator> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::set<int> first; + { + std::set<int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multiset<int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp b/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp new file mode 100644 index 0000000..d525b1a --- /dev/null +++ b/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
@@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <unordered_map> + +// class unordered_map + +// template <class H2, class P2> +// void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>&& source); +// template <class H2, class P2> +// void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>&& source); + +#include <unordered_map> +#include "test_macros.h" +#include "Counter.h" + +template <class Map> +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template <class T> +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash<T>()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_map<int, int> src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_map<int, int> dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {{5,0}})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_map<Counter<int>, int, throw_hasher<Counter<int>>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter<int> argument_type; + typedef size_t result_type; + size_t operator()(const Counter<int>& p) const + { + return std::hash<Counter<int>>()(p); + } + }; + { + typedef std::unordered_map<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type; + typedef std::unordered_map<Counter<int>, int, hasher, equal> second_map_type; + typedef std::unordered_multimap<Counter<int>, int, hasher, equal> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_map<int, int> first; + { + std::unordered_map<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multimap<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp new file mode 100644 index 0000000..d018620 --- /dev/null +++ b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <unordered_map> + +// class unordered_multimap + +// template <class H2, class P2> +// void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>&& source); +// template <class H2, class P2> +// void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>&& source); + +#include <unordered_map> +#include "test_macros.h" +#include "Counter.h" + +template <class Map> +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template <class T> +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash<T>()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_multimap<Counter<int>, int, throw_hasher<Counter<int>>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter<int> argument_type; + typedef size_t result_type; + size_t operator()(const Counter<int>& p) const + { + return std::hash<Counter<int>>()(p); + } + }; + { + typedef std::unordered_multimap<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type; + typedef std::unordered_multimap<Counter<int>, int, hasher, equal> second_map_type; + typedef std::unordered_map<Counter<int>, int, hasher, equal> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_multimap<int, int> first; + { + std::unordered_multimap<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_map<int, int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/unord/unord.multiset/merge.pass.cpp b/test/std/containers/unord/unord.multiset/merge.pass.cpp new file mode 100644 index 0000000..0bf8d35 --- /dev/null +++ b/test/std/containers/unord/unord.multiset/merge.pass.cpp
@@ -0,0 +1,158 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <unordered_set> + +// class unordered_multiset + +// template <class H2, class P2> +// void merge(unordered_set<key_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_set<key_type, H2, P2, allocator_type>&& source); +// template <class H2, class P2> +// void merge(unordered_multiset<key_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_multiset<key_type, H2, P2, allocator_type>&& source); + +#include <unordered_set> +#include "test_macros.h" +#include "Counter.h" + +template <class Set> +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template <class T> +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash<T>()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multiset<int> src{1, 3, 5}; + std::unordered_multiset<int> dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {})); + assert(set_equal(dst, {1, 2, 3, 4, 5, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_multiset<Counter<int>, throw_hasher<Counter<int>>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter<int> argument_type; + typedef size_t result_type; + size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); } + }; + { + typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type; + typedef std::unordered_multiset<Counter<int>, hasher, equal> second_set_type; + typedef std::unordered_set<Counter<int>, hasher, equal> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_multiset<int> first; + { + std::unordered_multiset<int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_set<int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} diff --git a/test/std/containers/unord/unord.set/merge.pass.cpp b/test/std/containers/unord/unord.set/merge.pass.cpp new file mode 100644 index 0000000..ebf03cd --- /dev/null +++ b/test/std/containers/unord/unord.set/merge.pass.cpp
@@ -0,0 +1,158 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// <unordered_set> + +// class unordered_set + +// template <class H2, class P2> +// void merge(unordered_set<key_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_set<key_type, H2, P2, allocator_type>&& source); +// template <class H2, class P2> +// void merge(unordered_multiset<key_type, H2, P2, allocator_type>& source); +// template <class H2, class P2> +// void merge(unordered_multiset<key_type, H2, P2, allocator_type>&& source); + +#include <unordered_set> +#include "test_macros.h" +#include "Counter.h" + +template <class Set> +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template <class T> +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash<T>()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_set<int> src{1, 3, 5}; + std::unordered_set<int> dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {5})); + assert(set_equal(dst, {1, 2, 3, 4, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_set<Counter<int>, throw_hasher<Counter<int>>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter<int> argument_type; + typedef size_t result_type; + size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); } + }; + { + typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type; + typedef std::unordered_set<Counter<int>, hasher, equal> second_set_type; + typedef std::unordered_multiset<Counter<int>, hasher, equal> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_set<int> first; + { + std::unordered_set<int> second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multiset<int> second; + first.merge(second); + first.merge(std::move(second)); + } + } +} 